package primary.primary0;

import offer.offer02.TreeNode;

public class S0098验证搜索二叉树 {

    /**
     * 中序遍历是升序的就是二叉搜索树
     * 所以只需要中序遍历一下，如果不严格升序就不是二叉搜索树
     */


    /**
     * 答案
     * 靠，没想起来可以把父节点的值往下传
     * 然后这里用的是long，因为有个用例它节点值是-Integer.MIN_VALUE
     */
    class Solution1 {
        public boolean isValidBST(TreeNode root) {
            return isValidBST(root, Long.MIN_VALUE, Long.MAX_VALUE);
        }

        public boolean isValidBST(TreeNode node, long lower, long upper) {
            if (node == null) {
                return true;
            }
            if (node.val <= lower || node.val >= upper) {
                return false;
            }
            return isValidBST(node.left, lower, node.val) && isValidBST(node.right, node.val, upper);
        }
    }


    public static class Solution {
        /**
         * 100
         * 一个数是二叉搜索树 == 左子树是 && 右子树是 && 当前值比左子树最大值大 && 当前值比右子树最小值小
         */
        public boolean isValidBST(TreeNode root) {
            return judgeNode(root).BST;
        }

        private Record judgeNode(TreeNode node){
            if(node == null){
                return null;
            }

            Record leftRecord = judgeNode(node.left);
            Record rightRecord = judgeNode(node.right);
            Record curRecord = new Record();

            if(leftRecord == null && rightRecord == null){
                curRecord.max = node.val;
                curRecord.min = node.val;
                curRecord.BST = true;
                return curRecord;
            }else if(leftRecord == null && rightRecord != null){
                // 子树为bst
                if(!rightRecord.BST){
                    return curRecord;
                }
                // 当前也为bst
                if(node.val < rightRecord.min){
                    curRecord.max = rightRecord.max;
                    curRecord.min = node.val;
                    curRecord.BST = true;
                    return curRecord;
                }else{
                    return curRecord;
                }
            }else if(leftRecord != null && rightRecord == null){
                // 子树为bst
                if(!leftRecord.BST){
                    return curRecord;
                }
                // 当前也为bst
                if(node.val > leftRecord.max){
                    curRecord.max = node.val;
                    curRecord.min = leftRecord.min;
                    curRecord.BST = true;
                    return curRecord;
                }else{
                    return curRecord;
                }
            }else{
                // 子树为bst
                if(!leftRecord.BST || !rightRecord.BST){
                    return curRecord;
                }
                // 当前也为bst
                if(node.val > leftRecord.max && node.val < rightRecord.min){
                    curRecord.max = rightRecord.max;
                    curRecord.min = leftRecord.min;
                    curRecord.BST = true;
                    return curRecord;
                }else{
                    return curRecord;
                }
            }

        }

        public class Record{
            public int max;
            public int min;
            public boolean BST;
            Record(int max, int min, boolean BST){
                this.max = max;
                this.min = min;
                this.BST = BST;
            }
            Record(){}
        }
    }
}
